package com.justnow;

import java.util.*;

/**
 * @author justnow
 * Created on 2020-09-23
 * Description
 */
public class GenShuiXue01 {

    static List<List<String>> mergeAccount(List<List<String>> accounts) {
        // 在此处编写实现代码逻辑
        List<List<String>> res = new ArrayList<>();
        if (accounts == null || accounts.size() <= 0) {
            return res;
        }

        Map<String, Integer> map = new HashMap<>();
        int n = accounts.size();
        UnionFind un = new UnionFind(n);
        for (int i = 0; i < n; i++) {
            List<String> list = accounts.get(i);
            for (int j = 0; j < list.size(); j++) {
                String s = list.get(j);
                if (map.containsKey(s)) {
                    int combine = map.get(s);
                    un.combine(combine, i);
                }
                map.put(s, i);
            }
        }
        Map<Integer, Set<String>> map1 = new HashMap<>();
        for (int i = 0; i < n; i++) {
            int index = un.find(i);
            List<String> person = accounts.get(i);
            List<String> str = person.subList(1, person.size());
            if (map1.containsKey(index)) {
                map1.get(index).addAll(str);
            } else {
                map1.put(index, new TreeSet<>(str));
            }
        }

        for (Map.Entry<Integer, Set<String>> integerSetEntry : map1.entrySet()) {
            List<String> temp = new ArrayList<>();
            int index = integerSetEntry.getKey();
            String name = accounts.get(index).get(0);
            temp.add(name);
            temp.addAll(integerSetEntry.getValue());
            res.add(temp);
        }

        return res;

    }
    
}

class UnionFind {
    int[] unionFind;
    public UnionFind(int n) {
        unionFind = new int[n];
        init();
    }
    public void init() {
        for (int i = 0; i < unionFind.length; i++) {
            unionFind[i] = -1;
        }
    }
    public int find(int x) {
        if (unionFind[x] < 0) {
            return x;
        } else {
            unionFind[x] = find(unionFind[x]);
        }
        return unionFind[x];
    } 
    public void combine(int x, int y) {
        int rootx = find(x);
        int rooty = find(y);
        if (rootx != rooty) {
            unionFind[rooty] = rootx;
        }
    }
    
    
    
}
